package two.recurtion;

import java.util.ArrayList;
import java.util.List;

/**
 * 全排列：
 *      给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
 * 时间复杂度：O(n!)
 * 思路：全排列，递归（边界、本层逻辑、子问题、还原现场）
 *      1）依次考虑每个位置放哪个数
 *      2）从“还没用的数”中选一个放在当前位置上
 */
public class Permute {
    public List<List<Integer>> permute(int[] nums) {
        ans = new ArrayList<List<Integer>>();
        process = new ArrayList<Integer>();
        this.nums = nums;
        used = new boolean[nums.length];
        find(0);
        return ans;
    }
    private void find(int index){
        if(index == nums.length){
            ans.add(new ArrayList<Integer>(process));
            return;
        }
        for(int i = 0; i < nums.length; i++){
            if(!used[i]){//如果位置i的元素没有被使用，则可以被index选择
                //处理本层逻辑
                process.add(nums[i]);
                used[i] = true; //已被使用
                //子问题
                find(index + 1);
                //还原现场
                used[i] = false; //未被使用
                process.remove(process.size() - 1);
            }
        }
    }

    private List<List<Integer>> ans; //结果集
    private List<Integer> process; //过程结果集
    private int[] nums;
    private boolean[] used; //已经被使用过的
}
